首页 题解 洛谷

# 函数调用

操作三的存在就相当于给操作建了一个树，那先想没有操作三。没有操作三，那每个操作之间都是独立的，一次操作二可以使前面的加法翻倍，那么就倒着做，算出这个操作一所带的乘法系数。

那么加上了操作三，就大概以操作三为根节点，他所包含的函数为叶子节点，进行一次拓扑排序，得到拓扑序，那就可以倒着做，把乘法系数往上传递，最后得到这个操作三的总的乘法系数。

Code
void toposort(){
	for(int i=1;i<=m;i++){
		if(!ru[i]){
			q.push(i);
		}
	}
	while(!q.empty()){
		int k=q.front();
        q.pop();
		topo[++tot]=k;
		for(int i=head[k];i;i=p[i].nex){
			int to=p[i].to;
			ru[to]--;
			if(!ru[to]){
				q.push(to);
			}
		}
	}
}
void get_mul(){
	for(int i=m;i>=1;i--){
		int k=topo[i];
		for(int j=head[k];j;j=p[j].nex){
			int to=p[j].to;
			b[k].mul=b[k].mul*b[to].mul%mod;// 得到总的乘法系数
		}
	}
}

这样就处理完部分所构成函数调用的树的每个节点所带的乘法系数，那么我们还需要处理题目所给出的函数操作序列，那我们只需要倒着枚举一边，依次把乘法系数累乘起来。这里的 sumsum 是指的这个操作后面的操作对他产生的影响，与上文的 toposorttoposort 和 getmulget_mul 所得到的 mulmul 是分开记的。

long long sum=1;
	for(int i=k;i>=1;i--){
		int x=pur[i];
		b[x].sum=(b[x].sum+sum)%mod;
		sum=sum*b[x].mul%mod;
	}

那么操作三所受到了影响，那以操作三为根的树的节点肯定也收到了影响，所以我们需要把这个 sumsum 下传，下传的时候，在对于同一个节点，他有多个儿子，但其实这些儿子的操作也是有先后性的，比如 +2,*2,*3 这个，你需要把 *2,*3 的这两个乘法系数加到 +2 中，根据链式前向星，早连接的边会晚遍历，所以我们正好再记一下。

void get_sum(){
	for(int i=1;i<=m;i++){
		int k=topo[i];
		long long sum=1;// 记住
		for(int j=head[k];j;j=p[j].nex){
			int to=p[j].to;
			b[to].sum=(b[to].sum+b[k].sum*sum%mod)%mod;
            sum=sum*b[to].mul%mod;
		}
	}
}

那该进行的都进行了，就可以统计答案啦。

因为之前有在处理函数操作序列时得到的乘法系数，那么直接给序列乘上，那再处理加法，枚举之前的操作，如果是操作一就进行一下操作:

a[b[i].p]=(a[b[i].p]+(b[i].v∗b[i].sum));p,v与题目要求一致，sum就是下放得到的a[b[i].p]=(a[b[i].p]+(b[i].v*b[i].sum)); \\ \text{p,v与题目要求一致，$sum$ 就是下放得到的}

就完结撒花啦✔️success

Code
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<queue>
#include<set>
#include<iomanip>
#define int long long
using namespace std;
const int MAXN=1e5+10;
const int mod=998244353;
struct node{
	int opt,p,v,j,mul,sum;
}b[MAXN];
struct edge{
	int nex,to;
}p[MAXN];
int cnt,head[MAXN],n,m,tot;
int topo[MAXN],ru[MAXN],pur[MAXN];
int a[MAXN];
void add(int from,int to){
	p[++cnt]=edge{head[from],to};
	head[from]=cnt;
}
queue<int> q;
void toposort(){
	for(int i=1;i<=m;i++){
		if(!ru[i]){
			q.push(i);
		}
	}
	while(!q.empty()){
		int k=q.front();
        q.pop();
		topo[++tot]=k;
		for(int i=head[k];i;i=p[i].nex){
			int to=p[i].to;
			ru[to]--;
			if(!ru[to]){
				q.push(to);
			}
		}
	}
}
void get_mul(){
	for(int i=m;i>=1;i--){
		int k=topo[i];
		for(int j=head[k];j;j=p[j].nex){
			int to=p[j].to;
			b[k].mul=b[k].mul*b[to].mul%mod;
		}
	}
}
void get_sum(){
	for(int i=1;i<=m;i++){
		int k=topo[i];
		long long sum=1;
		for(int j=head[k];j;j=p[j].nex){
			int to=p[j].to;
			b[to].sum=(b[to].sum+b[k].sum*sum%mod)%mod;
            sum=sum*b[to].mul%mod;
		}
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>b[i].opt;
		if(b[i].opt==1){
			cin>>b[i].p>>b[i].v;
			b[i].mul=1;
		}
		if(b[i].opt==2){
			cin>>b[i].v;
			b[i].mul=b[i].v;
		}
		if(b[i].opt==3){
			cin>>b[i].p;b[i].mul=1;
			for(int j=1;j<=b[i].p;j++){
				int x;
				cin>>x;
				add(i,x);	
				ru[x]++;
			}
			
		}
	}
	int k;
	cin>>k;
	for(int i=1;i<=k;i++){
		cin>>pur[i];
	}
	toposort();
	get_mul();
	long long sum=1;
	for(int i=k;i>=1;i--){
		int x=pur[i];
		b[x].sum=(b[x].sum+sum)%mod;// 刷出来 加法操作所带的总的 mul 
		sum=sum*b[x].mul%mod;
	}
	get_sum();
	for(int i=1;i<=n;i++){
		a[i]=a[i]*sum%mod;
	}
	for(int i=1;i<=m;i++){
		if(b[i].opt==1){
			a[b[i].p]=(a[b[i].p]+(b[i].v*b[i].sum)%mod)%mod;
		}
	}
	for(int i=1;i<=n;i++){
		cout<<a[i]%mod<<" ";    
	}
}